#include <iostream>
#include <fstream>
#include <cstring>

#include "lex.hpp"

using namespace std;

const char *char_name[] = {
	"LETTER",		// 字母
	"UNDERLINE",	// _
	"DIGIT",		// 数字

	"ADD",			// +
	"SUB",			// -
	"MUL",			// *
	"DIV",			// /
	"MOD",			// %
	"EQ",			// =
	"GT",			// >
	"LT",			// <
	"NOT",			// !
	"AND",			// &
	"OR",			// |

	"LBRAC",		// (
	"RBRAC",		// )
	"LCBRAC",		// {
	"RCBRAC",		// }
	"COMMA",		// ,
	"SEMI",			// ;

	"EPSILON",		// 空
};

// 打印状态类型
void print_states(int state_num, int char_num, map<int, int> &state_types) {
	cout << "Start state: ";  
	for (int i = 0; i < state_num; ++i) {
		if (state_types[i] == StateType::START) {
			cout << i << " ";
		}
	}
	cout << endl;

	cout << "Inter state: ";  
	for (int i = 0; i < state_num; ++i) {
		if (state_types[i] == StateType::INTER) {
			cout << i << " ";
		}
	}
	cout << endl;

	cout << "Exit state: ";  
	for (int i = 0; i < state_num; ++i) {
		if (state_types[i] == StateType::EXIT) {
			cout << i << " ";
		}
	}
	cout << endl;
	
	cout << "\t";
	for (int i = 0; i < char_num; ++i) {
		cout << char_name[i] << "\t";
	}
	cout << endl;
}

// 打印自动机的规则
static void print_nfa(
		int state_num, int char_num, 
		map<int, int> &state_types,
		vector<map<int, vector<int>>> &rules
	) {
	print_states(state_num, char_num, state_types);

	for (int i = 0; i < state_num; ++i) {
		cout << "State" << i << "\t";
		for (int j = 0; j < char_num; ++j) {
			auto res = rules[i].find(j);
			if (res == rules[i].end()) {
				cout << "{}";
			}else {
				vector<int> dst = (*res).second;
				for (auto iter = dst.begin(); iter != dst.end(); ++iter) {
					if (iter != dst.begin())
						cout << ",";
					cout << *iter;
				}
			}
			cout << "\t";
		}
		cout << endl;
	}
}

NFA::NFA(const char *rule_file) {
	cout << endl << "Building NFA from " << rule_file << "..." << endl;

	ifstream input(rule_file);

	input >> state_num >> char_num;

	// 退出状态个数
	int end_states;
	input >> end_states;

	int ind;
	input >> ind;
	state_types[ind] = StateType::START;

	for (int i = 0; i < end_states; ++i) { // 读取退出状态
		int ind, val;
		input >> ind >> val;
		state_types[ind] = StateType::EXIT;
		state_vals[ind] = val;
	}

	for (int i = 0; i < state_num; ++i) { // 其余状态即为中间状态
		rules.push_back(map<int, vector<int>>());
		if (state_types.find(i) == state_types.end()) {
			state_types[i] = StateType::INTER;
		}
	}

	// 读取
	char buff[50];
	for (int i = 0; i < state_num; ++i) {
		for (int j = 0; j < char_num; ++j) {
			input >> buff;
			if (strcmp(buff, "{}") != 0) { // “{}”表示没有可转移的状态
				const char *sep = ",";
				char *tmp = NULL;
				for (tmp = strtok(buff, sep); tmp != NULL; tmp = strtok(NULL, sep)) {
					int dst = stoi(tmp);
					if (rules[i].find(j) == rules[i].end()) {
						rules[i][j] = vector<int>();
					}
					rules[i][j].push_back(dst);
				}
			}
		}
	}

	input.close();

	cout << "Finished" << endl << endl;
}

void NFA::print_rules() {
	print_nfa(state_num, char_num, state_types, rules);
}

// 计算闭包
void NFA::closure(const unordered_set<int> &init, unordered_set<int> &result) const {
	result.clear();

	deque<int> que;
	int epsilon = char_num-1; // 最后一个符号默认空

	for (auto i = init.begin(); i != init.end(); ++i) { // 添加初始状态到闭包
		que.push_back(*i);
		result.insert(*i);
	}

	while (!que.empty()) {
		int i = que.front();
		que.pop_front();
		auto res = rules[i].find(epsilon);
		if (res != rules[i].end()) { // 有可转移状态
			const vector<int> &dst = (*res).second;
			for (auto j = dst.begin(); j != dst.end(); ++j) {
				if(result.find(*j) == result.end()) { // 可转移状态未加入闭包
					int k = *j;
					result.insert(k);
					que.push_back(k);
				}
			}
		}
	}
}

// 计算状态转移
void NFA::go(const unordered_set<int> &src, CharType ty, unordered_set<int> &dst) const {
	dst.clear();

	int ind = int(ty);
	for (auto i = src.begin(); i != src.end(); ++i) { // 遍历出发状态
		auto res = rules[*i].find(ind);
		if (res != rules[*i].end()) { // 有可转移状态
			const vector<int> &dsts = (*res).second;
			for (auto j = dsts.begin(); j != dsts.end(); ++j) {
				if (dst.find(*j) == dst.end()) { // 可转移状态未加入闭包
					dst.insert(*j);
				}
			}
		}
	}
}

int NFA::get_state_type(int state) {
	int res = state_types[state];
	return res;
}

int NFA::get_state_val(int state) {
	int res = state_vals[state];
	return res;
}
